/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-11-15
 * Time:12:00
 */
//从中序和后序遍历序列构造二叉树
//给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。
//思路：思路与前序和中序的一样，只不过前序序列中是从第一个节点值开始为根root，但是在后序序列中是从最后一个节点开始为根root(左子树-右子树-根),所以
//后序遍历和中序遍历构造二叉树的方式是先创建右子树，再创建左子树。
public class UsePostorderAndInorderCreateTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int postIndex;

    public TreeNode buildTree(int[] inorder,int[] postorder) {
        postIndex = postorder.length-1;
        return bulidTreeChild(inorder,postorder,0,inorder.length-1);
    }

    public TreeNode bulidTreeChild(int[] inorder,int[] postorder,int inBegin,int inEnd) {
        if (inBegin > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postIndex]);

        int rootIndex = findVal(inorder,inBegin,inEnd,postorder[postIndex]);

        postIndex--;

        root.right = bulidTreeChild(inorder,postorder,rootIndex+1,inEnd);
        root.left = bulidTreeChild(inorder,postorder,inBegin,rootIndex-1);

        return root;
    }

    public int findVal(int[] inorder,int inBegin,int inEnd,int val) {
        for (int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}
